package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/diagonal-traverse/description/?envType=daily-question&envId=2025-08-25
 * @create 2025/8/25 09:02
 * @since JDK17
 */

public class Solution54 {
    public int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length, m = mat[0].length, len = n * m, cnt = 0, k = 0;
        int[] ans = new int[len];
        int[][]dire = new int[][]{{-1, 1}, {1, -1}};
        int x = 0, y = 0, nx, ny;
        while (cnt < len) {
            ans[cnt++] = mat[x][y];
            nx = x + dire[k][0];
            ny = y + dire[k][1];
            if (nx == -1 || nx == n || ny == -1 || ny == m) {   // 越界
                if (k == 0) {
                    if (y != m - 1) {
                        y++;
                    } else {
                        x++;
                    }
                } else {
                    if (y == 0) {
                        x++;
                    } else {
                        y++;
                    }
                }
                k = 1 - k;
            } else {
                x = nx;
                y = ny;
            }
        }

        return ans;
    }
}
